The evidence available on the spread of Islam in Southeast Asia is reliant on tombstones and scattered evidence. Significant examples include a Muslim tombstone found in Champa dating from early 11th century, an Islamic tombstone of Gresik (Java) dated late 11th century, the Trengganu stone dated 1303, records of Muslim settlers in Majapahit and a Muslim trading colony in Northern Malaya and of rulers in Pasai converting to Islam in 1282. By the end of the 15th century, Islam was firmly established in the Malay Peninsula, Sumatra, and northern coasts of Java, Brunei and North Borneo. It was also penetrating the Spice Islands e.g. the Moluccas and the Sulu Archipelago.
In the 11th century, a turbulent period occurred in the history of Malay Archipelago, the Chola Navy crossed the ocean and attacked the Srivijaya kingdom of Sangrama Vijayatungavarman, Kadaram (Kedah), an important forted city in the Malayan peninsula was sacked and the king was taken captive. Along with Kadaram, Pannai in Sumatra and Malaiyur (Melayu) in the Malayan peninsula were attacked too. Soon after that, the king of Kedah Phra Ong Mahawangsa became the first ruler to abandon the traditional Hindu faith, and converted to Islam with the Sultanate of Kedah established in year 1136. Samudera Pasai converted to Islam in the year 1267, and many other rulers follow suit.
Islam was mainly confined to Sumatran ports before the rise of Malacca. Evidence of the presence of Islam in these ports included a report in 1292 by Marco Polo that the states of Pasai and Perlak had Muslim rulers; a tombstone of a Pasai ruler who died in 1297 had the Islamic name of Malek-al-Salleh. These ports were among the earliest in Southeast Asia to be converted. The reasons for this early conversion include the distance of these areas from the influence of Hindu Majapahit, the long trading links these areas had with Indian traders who had converted to Islam (these converted Indians included those from the Coromandel Coast and those from Gujarat).